{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find a Value of a Mysterious Function Closest to Target"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #segment-tree #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #线段树 #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: closestToTarget"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到最接近目标值的函数值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/07/19/change.png\" style=\"height: 312px; width: 635px;\"></p>\n",
    "\n",
    "<p>Winston 构造了一个如上所示的函数&nbsp;<code>func</code>&nbsp;。他有一个整数数组&nbsp;<code>arr</code>&nbsp;和一个整数&nbsp;<code>target</code>&nbsp;，他想找到让&nbsp;<code>|func(arr, l, r) - target|</code>&nbsp;最小的 <code>l</code>&nbsp;和 <code>r</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回&nbsp;<code>|func(arr, l, r) - target|</code>&nbsp;的最小值。</p>\n",
    "\n",
    "<p>请注意，&nbsp;<code>func</code> 的输入参数&nbsp;<code>l</code> 和&nbsp;<code>r</code>&nbsp;需要满足&nbsp;<code>0 &lt;= l, r &lt; arr.length</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [9,12,3,7,15], target = 5\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>所有可能的 [l,r] 数对包括 [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]]， Winston 得到的相应结果为 [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0] 。最接近 5 的值是 7 和 3，所以最小差值为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1000000,1000000,1000000], target = 1\n",
    "<strong>输出：</strong>999999\n",
    "<strong>解释：</strong>Winston 输入函数的所有可能 [l,r] 数对得到的函数值都为 1000000 ，所以最小差值为 999999 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1,2,4,8,16], target = 0\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 10^6</code></li>\n",
    "\t<li><code>0 &lt;= target &lt;= 10^7</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-a-value-of-a-mysterious-function-closest-to-target](https://leetcode.cn/problems/find-a-value-of-a-mysterious-function-closest-to-target/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-a-value-of-a-mysterious-function-closest-to-target](https://leetcode.cn/problems/find-a-value-of-a-mysterious-function-closest-to-target/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[9,12,3,7,15]\\n5', '[1000000,1000000,1000000]\\n1', '[1,2,4,8,16]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        S = set();res = inf\n",
    "        for i in arr:\n",
    "            newS = set([i])\n",
    "            for x in S:\n",
    "                newS.add(x&i)\n",
    "            for x in newS:\n",
    "                res = min(res,abs(x-target))\n",
    "            S = newS\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        basket = set()\n",
    "        res = abs(arr[0] - target)\n",
    "        for num in arr:\n",
    "            if num == target:\n",
    "                return 0\n",
    "\n",
    "            if num < target:\n",
    "                res = min(res, target - num)\n",
    "                res = reduce(lambda a, b: min(a, b - target), basket, res)\n",
    "                basket = set()\n",
    "                continue\n",
    "\n",
    "            basket2 = {num}\n",
    "            for v in basket:\n",
    "                tmp = v & num\n",
    "                \n",
    "                if tmp == target:\n",
    "                    return 0\n",
    "                \n",
    "                if tmp < target:\n",
    "                    res = min(res, v - target)\n",
    "                    res = min(res, target - tmp)\n",
    "                else:    \n",
    "                    basket2.add(tmp)\n",
    "            basket = basket2\n",
    "        return reduce(lambda a, b: min(a, abs(b-target)), basket, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans = abs(arr[0]-target)\n",
    "        set = {arr[0]}\n",
    "        for num in arr[1:]:\n",
    "            set = {x & num for x in set} | {num}  \n",
    "            ans = min(ans, min(abs(x - target) for x in set))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        basket = set()\n",
    "        res = abs(arr[0] - target)\n",
    "        for num in arr:\n",
    "            if num == target:\n",
    "                return 0\n",
    "\n",
    "            if num < target:\n",
    "                res = min(res, target - num)\n",
    "                res = reduce(lambda a, b: min(a, b - target), basket, res)\n",
    "                basket = set()\n",
    "                continue\n",
    "\n",
    "            basket2 = {num}\n",
    "            for v in basket:\n",
    "                tmp = v & num\n",
    "                if tmp == target:\n",
    "                    return 0\n",
    "                if tmp < target:\n",
    "                    res = min(res, v - target)\n",
    "                    res = min(res, target - tmp)\n",
    "                else:\n",
    "                    basket2.add(tmp)\n",
    "            basket = basket2\n",
    "        return reduce(lambda a, b: min(a, abs(b - target)), basket, res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func2(arr, target):\n",
    "    basket = set()\n",
    "    res = abs(arr[0] - target)\n",
    "    for num in arr:\n",
    "        if num == target:\n",
    "            return 0\n",
    "\n",
    "        if num < target:\n",
    "            res = min(res, target - num)\n",
    "            res = reduce(lambda a, b: min(a, b - target), basket, res)\n",
    "            basket = set()\n",
    "            continue\n",
    "\n",
    "        basket2 = {num}\n",
    "        for v in basket:\n",
    "            tmp = v & num\n",
    "\n",
    "            if tmp == target:\n",
    "                return 0\n",
    "            \n",
    "            if tmp < target:\n",
    "                res = min(res, v - target)\n",
    "                res = min(res, target - tmp)\n",
    "            else:\n",
    "                basket2.add(tmp)\n",
    "        basket = basket2\n",
    "    return reduce(lambda a, b: min(a, abs(b-target)), basket, res)\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        return func2(arr,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans = abs(arr[0]-target)\n",
    "        set = {arr[0]}\n",
    "        for num in arr[1:]:\n",
    "            set = {x & num for x in set} | {num}  # a={1}|{4} a={1,4}\n",
    "            ans = min(ans, min(abs(x - target) for x in set))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        s={arr[0]}\n",
    "        n=len(arr)\n",
    "        cmin=abs(target-arr[0])\n",
    "        for i in range(1,n):\n",
    "            d={arr[i]}\n",
    "            cmin=min(cmin,abs(target-arr[i]))\n",
    "            for j in s:\n",
    "                t=j&arr[i]\n",
    "                cmin=min(cmin,abs(t-target))\n",
    "                d.add(t)\n",
    "            s=d\n",
    "        return cmin"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans=abs(arr[0]-target)\n",
    "        temp={arr[0]}\n",
    "        for item in arr:\n",
    "            temp={item & num for num in temp} | {item}\n",
    "            ans=min(ans,min(abs(num-target) for num in temp))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ret = 20e7\n",
    "        pre_sum = set()\n",
    "        for num in arr:\n",
    "            pre_sum.add(num)\n",
    "            pre_sum = [x & num for x in pre_sum]\n",
    "            pre_sum = set(pre_sum)\n",
    "            ret = min(ret, min(abs(x - target) for x in pre_sum))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans = abs(arr[0] - target)\n",
    "        valid = {arr[0]}\n",
    "        for num in arr[1:]:\n",
    "            valid = {x & num for x in valid} | {num}\n",
    "            ans = min(ans, min(abs(x - target) for x in valid))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans = abs(arr[0] + target)\n",
    "        valid = {arr[0]}\n",
    "        for num in arr:\n",
    "            valid = {x & num for x in valid} | {num}\n",
    "            ans = min(ans, min(abs(x - target) for x in valid))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        res = inf\n",
    "        ands = []\n",
    "        n = len(arr)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = arr[i]\n",
    "            ands.append([(1 << 20) - 1, i])\n",
    "            # for p in ands:\n",
    "            #     p[0] &= x \n",
    "            # print(ands)\n",
    "            k = 0 \n",
    "            for p in ands:\n",
    "                p[0] &= x\n",
    "                if ands[k][0] == p[0]:\n",
    "                    ands[k][1] = p[1]\n",
    "                else:\n",
    "                    k += 1\n",
    "                    ands[k] = p \n",
    "            del ands[k + 1:]\n",
    "            for an, _ in ands:\n",
    "                res = min(res, abs(target - an))\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        basket = set()\n",
    "        res = abs(arr[0] - target)\n",
    "        for num in arr:\n",
    "            if num == target:\n",
    "                return 0\n",
    "\n",
    "            if num < target:\n",
    "                res = min(res, target - num)\n",
    "                res = reduce(lambda a, b: min(a, b - target), basket, res)\n",
    "                basket = set()\n",
    "                continue\n",
    "\n",
    "            basket2 = {num}\n",
    "            for v in basket:\n",
    "                tmp = v & num\n",
    "\n",
    "                if tmp == target:\n",
    "                    return 0\n",
    "                \n",
    "                if tmp < target:\n",
    "                    res = min(res, v - target)\n",
    "                    res = min(res, target - tmp)\n",
    "                else:\n",
    "                    basket2.add(tmp)\n",
    "            basket = basket2\n",
    "        return reduce(lambda a, b: min(a, abs(b-target)), basket, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        st=[]\n",
    "        res=inf\n",
    "        for i,a in enumerate(arr):\n",
    "            for j in range(len(st)):\n",
    "                st[j][0]=st[j][0]&a\n",
    "            nst=[]\n",
    "            for v,j in st:\n",
    "                if len(nst)==0 or v!=nst[-1][0]:\n",
    "                    nst.append([v,j])\n",
    "                    res=min(res,abs(v-target))\n",
    "            nst.append([a,i])\n",
    "            res=min(res,abs(a-target))\n",
    "            st=nst\n",
    "            if len(st)>1 and st[-1][0]==st[-2][0]:\n",
    "                st.pop()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        basket = set()\n",
    "        res = abs(arr[0] - target)\n",
    "        for num in arr:\n",
    "            if num == target:\n",
    "                return 0\n",
    "            basket2 = {num}\n",
    "            res = min(res, abs(target - num))\n",
    "            for v in basket:\n",
    "                tmp = v & num\n",
    "                if tmp == target:\n",
    "                    return 0\n",
    "                res = min(res, abs(target - tmp))\n",
    "                if tmp <= target:\n",
    "                    continue\n",
    "                basket2.add(tmp)\n",
    "            basket = basket2\n",
    "        return reduce(lambda a, b: min(a, abs(b-target)), basket, res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        basket = set()\n",
    "        res = abs(arr[0] - target)\n",
    "        for num in arr:\n",
    "            if num == target:\n",
    "                return 0\n",
    "\n",
    "            if num < target:\n",
    "                res = min(res, target - num)\n",
    "                res = reduce(lambda a, b: min(a, b - target), basket, res)\n",
    "                basket = set()\n",
    "                continue\n",
    "\n",
    "            basket2 = {num}\n",
    "            for v in basket:\n",
    "                tmp = v & num\n",
    "                \n",
    "                if tmp == target:\n",
    "                    return 0\n",
    "                \n",
    "                if tmp < target:\n",
    "                    res = min(res, v - target)\n",
    "                    res = min(res, target - tmp)\n",
    "                else:    \n",
    "                    basket2.add(tmp)\n",
    "            basket = basket2\n",
    "        return reduce(lambda a, b: min(a, abs(b-target)), basket, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans = abs(arr[0] - target)\n",
    "        valid = {arr[0]}\n",
    "        for num in arr:\n",
    "            valid = {x & num for x in valid} | {num}\n",
    "            ans = min(ans, min(abs(x - target) for x in valid))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans=abs(arr[0]-target)\n",
    "        length=len(arr)\n",
    "        temp={arr[0]}\n",
    "        for j in range(1,length):\n",
    "            temp={arr[j] & num for num in temp} | {arr[j]}\n",
    "            ans=min(ans,min(abs(num-target) for num in temp))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func2(arr, target):\n",
    "    basket = set()\n",
    "    res = abs(arr[0] - target)\n",
    "    for num in arr:\n",
    "        if num == target:\n",
    "            return 0\n",
    "        basket2 = {num}\n",
    "        res = min(res, abs(target - num))\n",
    "        for v in basket:\n",
    "            tmp = v & num\n",
    "            if tmp == target:\n",
    "                return 0\n",
    "            res = min(res, abs(target - tmp))\n",
    "            if tmp <= target:\n",
    "                continue\n",
    "            basket2.add(tmp)\n",
    "        basket = basket2\n",
    "    return reduce(lambda a, b: min(a, abs(b-target)), basket, res)\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        return func2(arr,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans = abs(arr[0] - target)\n",
    "        s = {arr[0]}\n",
    "        for x in arr:\n",
    "            s = {x & y for y in s} | {x}\n",
    "            ans = min(ans, min(abs(y - target) for y in s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        basket = set()\n",
    "        res = abs(arr[0] - target)\n",
    "        for num in arr:\n",
    "            if num == target:\n",
    "                return 0\n",
    "            basket2 = {num}\n",
    "            res = min(res, abs(target - num))\n",
    "            for v in basket:\n",
    "                tmp = v & num\n",
    "                res = min(res, abs(target - tmp))\n",
    "                if tmp <= target:\n",
    "                    continue\n",
    "                else:\n",
    "                    basket2.add(tmp)\n",
    "            basket = basket2\n",
    "        return reduce(lambda a, b: min(a, abs(b-target)), basket, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        pre = set()\n",
    "        ans = math.inf\n",
    "        for v in arr:\n",
    "            cur = {v} | {w & v for w in pre}\n",
    "            a = min(abs(x - target) for x in cur)\n",
    "            ans = min(ans, a)\n",
    "            pre = cur\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef closestToTarget(self, arr, target):\n",
    "\t\tbasket = set()\n",
    "\t\tres = abs(arr[0] - target)\n",
    "\t\tfor num in arr:\n",
    "\t\t\tif num == target:\n",
    "\t\t\t\treturn 0\n",
    "\n",
    "\t\t\tif num < target:\n",
    "\t\t\t\tres = min(res, target - num)\n",
    "\t\t\t\tres = reduce(lambda a, b: min(a, b - target), basket, res)\n",
    "\t\t\t\tbasket = set()\n",
    "\t\t\t\tcontinue\n",
    "\n",
    "\t\t\tbasket2 = {num}\n",
    "\t\t\tfor v in basket:\n",
    "\t\t\t\ttmp = v & num\n",
    "\n",
    "\t\t\t\tif tmp == target:\n",
    "\t\t\t\t\treturn 0\n",
    "\n",
    "\t\t\t\tif tmp < target:\n",
    "\t\t\t\t\tres = min(res, v - target)\n",
    "\t\t\t\t\tres = min(res, target - tmp)\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tbasket2.add(tmp)\n",
    "\t\t\tbasket = basket2\n",
    "\t\treturn reduce(lambda a, b: min(a, abs(b - target)), basket, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans = abs(arr[0] - target)\n",
    "        valid = {arr[0]}\n",
    "        for num in arr:\n",
    "            valid = {x & num for x in valid} | {num}\n",
    "            ans = min(ans, min(abs(x - target) for x in valid))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans = abs(arr[0] - target)\n",
    "        valid = {arr[0]}\n",
    "        for num in arr:\n",
    "            valid = {x & num for x in valid} | {num}\n",
    "            ans = min(ans, min(abs(x - target) for x in valid))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        basket = set()\n",
    "        res = abs(arr[0] - target)\n",
    "        for num in arr:\n",
    "            if num == target:\n",
    "                return 0\n",
    "\n",
    "            if num < target:\n",
    "                res = min(res, target - num)\n",
    "                res = reduce(lambda a, b: min(a, b - target), basket, res)\n",
    "                basket = set()\n",
    "                continue\n",
    "\n",
    "            basket2 = {num}\n",
    "            for v in basket:\n",
    "                tmp = v & num\n",
    "\n",
    "                if tmp == target:\n",
    "                    return 0\n",
    "\n",
    "                if tmp < target:\n",
    "                    res = min(res, v - target)\n",
    "                    res = min(res, target - tmp)\n",
    "                else:\n",
    "                    basket2.add(tmp)\n",
    "            basket = basket2\n",
    "        return reduce(lambda a, b: min(a, abs(b - target)), basket, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans = abs(arr[0] + target)\n",
    "        valid = {arr[0]}\n",
    "        for num in arr:\n",
    "            valid = {x & num for x in valid} | {num}\n",
    "            ans = min(ans, min(abs(x - target) for x in valid))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans = abs(arr[0] - target)\n",
    "        valid = {arr[0]}\n",
    "        for num in arr[1:]:\n",
    "            valid = {x & num for x in valid} | {num}  # a={1}|{4} a={1,4}\n",
    "            ans = min(ans, min(abs(x - target) for x in valid))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        l,r=0,0\n",
    "        diff = inf\n",
    "        n = len(arr)\n",
    "        if arr[0] > target:\n",
    "            flag = 1\n",
    "            cur = arr[0]\n",
    "        elif arr[0] < target:\n",
    "            flag = 0\n",
    "        else:\n",
    "            return 0\n",
    "        # print(\"arr:\",arr)\n",
    "        while r < n:\n",
    "            if flag == 1:\n",
    "                last = inf\n",
    "                while cur > target:\n",
    "                    r += 1\n",
    "                    if r > n-1:\n",
    "                        diff =  min(abs(cur-target),diff)\n",
    "                        break\n",
    "                    last = cur\n",
    "                    cur = cur & arr[r]\n",
    "                diff = min(diff,abs(cur-target),abs(last-target))\n",
    "                if diff == 0:\n",
    "                    return 0\n",
    "                flag = 0\n",
    "            else:\n",
    "                if arr[r] < target:\n",
    "                    diff = min(diff,abs(arr[r]-target))\n",
    "                    r += 1\n",
    "                else:\n",
    "                    l = r\n",
    "                    cur = arr[l]\n",
    "                    while cur > target:\n",
    "                        l -= 1\n",
    "                        last = cur\n",
    "                        cur = cur & arr[l]\n",
    "                    diff = min(diff,abs(cur-target),abs(last-target))\n",
    "                    if diff == 0:\n",
    "                        return 0\n",
    "                    flag = 1 \n",
    "                    cur = last\n",
    "                    l += 1\n",
    "            # print(l,r,diff)\n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans = abs(arr[0] - target)\n",
    "        valid = {arr[0]}\n",
    "        for num in arr[1:]:\n",
    "            valid = {x & num for x in valid} | {num}\n",
    "            ans = min(ans, min(abs(x - target) for x in valid))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        N = max(arr).bit_length()\n",
    "        c = [0] * N\n",
    "        def c_update(v, inc):\n",
    "            for i in range(N):\n",
    "                if (v >> i) & 1 == 0:\n",
    "                    c[i] += inc\n",
    "            return functools.reduce(operator.add, (0 if c[i] else (1<<i) for i in range(N)))\n",
    "        \n",
    "        ans = math.inf\n",
    "        i = 0\n",
    "        for j,v in enumerate(arr):\n",
    "            x = c_update(v, 1)\n",
    "            ans = min(ans, abs(target - x))\n",
    "            while i < j and x < target:\n",
    "                x = c_update(arr[i], -1)\n",
    "                ans = min(ans, abs(target - x))\n",
    "                i += 1\n",
    "            if ans == 0: break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        l,r=0,0\n",
    "        diff = inf\n",
    "        n = len(arr)\n",
    "        if arr[0] > target:\n",
    "            flag = 1\n",
    "            cur = arr[0]\n",
    "        elif arr[0] < target:\n",
    "            flag = 0\n",
    "        else:\n",
    "            return 0\n",
    "        # print(\"arr:\",arr)\n",
    "        while r < n:\n",
    "            if flag == 1:\n",
    "                last = inf\n",
    "                while cur > target:\n",
    "                    r += 1\n",
    "                    if r > n-1:\n",
    "                        diff =  min(abs(cur-target),diff)\n",
    "                        break\n",
    "                    last = cur\n",
    "                    cur = cur & arr[r]\n",
    "                diff = min(diff,abs(cur-target),abs(last-target))\n",
    "                if diff == 0:\n",
    "                    return 0\n",
    "                flag = 0\n",
    "            else:\n",
    "                if arr[r] < target:\n",
    "                    diff = min(diff,abs(arr[r]-target))\n",
    "                    r += 1\n",
    "                else:\n",
    "                    l = r\n",
    "                    cur = arr[l]\n",
    "                    while cur > target:\n",
    "                        l -= 1\n",
    "                        last = cur\n",
    "                        cur = cur & arr[l]\n",
    "                    diff = min(diff,abs(cur-target),abs(last-target))\n",
    "                    if diff == 0:\n",
    "                        return 0\n",
    "                    flag = 1 \n",
    "                    cur = last\n",
    "                    l += 1\n",
    "            # print(l,r,diff)\n",
    "        return diff              \n",
    "\n",
    "                \n",
    "\n",
    "            \n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "\n",
    "        ans = abs(arr[0] - target)\n",
    "        s = {arr[0]}\n",
    "        for num in arr:\n",
    "            s = {num & t for t in s} | {num}\n",
    "            ans = min(ans, min(abs(t - target) for t in s))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        visit = [-1] * n\n",
    "        res = float(\"inf\") # 这是最大\n",
    "        for i,v in enumerate(arr):\n",
    "            assert v >= visit[i]\n",
    "            if v == visit[i]: continue\n",
    "            if v == target:\n",
    "                return 0\n",
    "            if v < target:\n",
    "                res = min(res, target - v)\n",
    "                continue\n",
    "            assert v > target\n",
    "            res = min(res, v - target)\n",
    "            for j in range(i + 1, n):\n",
    "                v = v & arr[j]\n",
    "                if v <= visit[j]: break\n",
    "                visit[j] = v\n",
    "                if v == target:\n",
    "                    return 0\n",
    "                if v < target:\n",
    "                    res = min(res, target - v)\n",
    "                    break\n",
    "                assert v > target\n",
    "                res = min(res, v - target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        visit = [-1] * n\n",
    "        res = float(\"inf\") # 这是最大\n",
    "        for i,v in enumerate(arr):\n",
    "            assert v >= visit[i]\n",
    "            if v == visit[i]: continue\n",
    "            #if i > 0 and v == arr[i-1]: continue\n",
    "            if v == target:\n",
    "                return 0\n",
    "            if v < target:\n",
    "                res = min(res, target - v)\n",
    "                continue\n",
    "            assert v > target\n",
    "            res = min(res, v - target)\n",
    "            for j in range(i + 1, n):\n",
    "                v = v & arr[j]\n",
    "                if v <= visit[j]: break\n",
    "                visit[j] = v\n",
    "                if v == target:\n",
    "                    return 0\n",
    "                if v < target:\n",
    "                    res = min(res, target - v)\n",
    "                    break\n",
    "                assert v > target\n",
    "                res = min(res, v - target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        visit = [-1] * n\n",
    "        res = float(\"inf\") # 这是最大\n",
    "        for i,v in enumerate(arr):\n",
    "            if v <= visit[i]:\n",
    "                continue\n",
    "            if v == target:\n",
    "                return 0\n",
    "            if v < target:\n",
    "                res = min(res, target - v)\n",
    "                continue\n",
    "            assert v > target\n",
    "            res = min(res, v - target)\n",
    "            for j in range(i + 1, n):\n",
    "                v = v & arr[j]\n",
    "                if v <= visit[j]:\n",
    "                    break\n",
    "                visit[j] = v\n",
    "                if v == target:\n",
    "                    return 0\n",
    "                if v < target:\n",
    "                    res = min(res, target - v)\n",
    "                    break\n",
    "                assert v > target\n",
    "                res = min(res, v - target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        visit = [-1] * n\n",
    "        res = float(\"inf\") # 这是最大\n",
    "        for i,v in enumerate(arr):\n",
    "            if v == visit[i]: continue\n",
    "            #if i > 0 and v == arr[i-1]: continue\n",
    "            if v == target:\n",
    "                return 0\n",
    "            if v < target:\n",
    "                res = min(res, target - v)\n",
    "                continue\n",
    "            assert v > target\n",
    "            res = min(res, v - target)\n",
    "            for j in range(i + 1, n):\n",
    "                v = v & arr[j]\n",
    "                if v <= visit[j]: break\n",
    "                visit[j] = v\n",
    "                if v == target:\n",
    "                    return 0\n",
    "                if v < target:\n",
    "                    res = min(res, target - v)\n",
    "                    break\n",
    "                assert v > target\n",
    "                res = min(res, v - target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        visit = [-1] * n\n",
    "        res = abs(arr[0] - target)\n",
    "        for i,v in enumerate(arr):\n",
    "            #if v == visit[i]: continue\n",
    "            #assert v > visit[i]\n",
    "            if v == target:\n",
    "                return 0\n",
    "            if v < target:\n",
    "                res = min(res, target - v)\n",
    "                continue\n",
    "            assert v > target\n",
    "            res = min(res, v - target)\n",
    "            for j in range(i + 1, n):\n",
    "                v = v & arr[j]\n",
    "                if v <= visit[j]: break\n",
    "                visit[j] = v\n",
    "                if v == arr[j]: break\n",
    "                if v == target:\n",
    "                    return 0\n",
    "                if v < target:\n",
    "                    res = min(res, target - v)\n",
    "                    break\n",
    "                assert v > target\n",
    "                res = min(res, v - target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        visit = [-1] * n\n",
    "        res = float(\"inf\") # 这是最大\n",
    "        for i,v in enumerate(arr):\n",
    "            if v <= visit[i]:\n",
    "                continue\n",
    "            if v == target:\n",
    "                return 0\n",
    "            if v < target:\n",
    "                res = min(res, target - v)\n",
    "                continue\n",
    "            assert v > target\n",
    "            res = min(res, v - target)\n",
    "            for j in range(i + 1, n):\n",
    "                nn = arr[j] & v\n",
    "                if nn <= visit[j]:\n",
    "                    break\n",
    "                visit[j] = nn\n",
    "                if nn == target:\n",
    "                    return 0\n",
    "                if nn < target:\n",
    "                    res = min(res, target - nn)\n",
    "                    break\n",
    "                v = nn\n",
    "                assert v > target\n",
    "                res = min(res, v - target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        l = len(arr)\n",
    "        visit = [-1 for i in range(l)]\n",
    "        res = float(\"inf\")\n",
    "        for i in range(l):\n",
    "            n = arr[i]\n",
    "            if n <= visit[i]:\n",
    "                continue\n",
    "            elif n == target:\n",
    "                return 0\n",
    "            elif n < target:\n",
    "                res = min(res, target - n)\n",
    "                continue\n",
    "            for j in range(i + 1, l):\n",
    "                nn = arr[j] & n\n",
    "                if nn <= visit[j]:\n",
    "                    break\n",
    "                visit[j] = nn\n",
    "                if nn == target:\n",
    "                    return 0\n",
    "                elif nn < target:\n",
    "                    res = min(res, target - nn)\n",
    "                    res = min(res, n - target)\n",
    "                    n = nn\n",
    "                    break\n",
    "                n = nn\n",
    "            if n > target:\n",
    "                res = min(res, n - target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        visit = [-1] * n\n",
    "        res = abs(arr[0] - target)\n",
    "        for i,v in enumerate(arr):\n",
    "            if v == visit[i]: continue\n",
    "            assert v > visit[i]\n",
    "            if v == target:\n",
    "                return 0\n",
    "            if v < target:\n",
    "                res = min(res, target - v)\n",
    "                continue\n",
    "            assert v > target\n",
    "            res = min(res, v - target)\n",
    "            for j in range(i + 1, n):\n",
    "                v = v & arr[j]\n",
    "                if v <= visit[j]: break\n",
    "                visit[j] = v\n",
    "                if v == target:\n",
    "                    return 0\n",
    "                if v < target:\n",
    "                    res = min(res, target - v)\n",
    "                    break\n",
    "                assert v > target\n",
    "                res = min(res, v - target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        visit = [-1] * n\n",
    "        res = abs(arr[0] - target)\n",
    "        for i,v in enumerate(arr):\n",
    "            #if v == visit[i]: continue\n",
    "            #assert v > visit[i]\n",
    "            if v == target:\n",
    "                return 0\n",
    "            if v < target:\n",
    "                res = min(res, target - v)\n",
    "                continue\n",
    "            assert v > target\n",
    "            res = min(res, v - target)\n",
    "            for j in range(i + 1, n):\n",
    "                v = v & arr[j]\n",
    "                if v == visit[j]: break\n",
    "                assert v > visit[j]\n",
    "                visit[j] = v\n",
    "                if v == arr[j]: break\n",
    "                if v == target:\n",
    "                    return 0\n",
    "                if v < target:\n",
    "                    res = min(res, target - v)\n",
    "                    break\n",
    "                assert v > target\n",
    "                res = min(res, v - target)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        seen = set()\n",
    "        tmp = set()\n",
    "        for a in arr:\n",
    "            to_add = {a}\n",
    "            for pre in tmp:\n",
    "                to_add.add(pre & a)\n",
    "            tmp = to_add\n",
    "            seen |= to_add\n",
    "        # seen.add(-inf)\n",
    "        # seen.add(inf)\n",
    "        # L = sorted(seen)\n",
    "        # idx = bisect_left(L, target)\n",
    "        return min(abs(x - target) for x in seen)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans, vis = set(), set()\n",
    "        for x in arr:\n",
    "            vis = {x & y for y in vis} | {x}\n",
    "            ans |= vis\n",
    "        return min(abs(x-target) for x in ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        seen = set()\n",
    "        tmp = set()\n",
    "        for a in arr:\n",
    "            to_add = {a}\n",
    "            for pre in tmp:\n",
    "                to_add.add(pre & a)\n",
    "            tmp = to_add\n",
    "            seen |= to_add\n",
    "        # seen.add(-inf)\n",
    "        # seen.add(inf)\n",
    "        # L = sorted(seen)\n",
    "        # idx = bisect_left(L, target)\n",
    "        return min(abs(x - target) for x in seen)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans = set()\n",
    "        ands = set()\n",
    "        for x in arr:\n",
    "            ands = {x & i for i in ands}\n",
    "            ands.add(x)\n",
    "            ans |= ands\n",
    "        return min(abs(target - x) for x in ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        seen = set()\n",
    "        tmp = set()\n",
    "        for a in arr:\n",
    "            to_add = {a}\n",
    "            for pre in tmp:\n",
    "                to_add.add(pre & a)\n",
    "            tmp = to_add\n",
    "            seen |= to_add\n",
    "        seen.add(-inf)\n",
    "        seen.add(inf)\n",
    "        L = sorted(seen)\n",
    "        idx = bisect_left(L, target)\n",
    "        return min(L[idx] - target, target - L[idx - 1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        ans = set()\n",
    "        tmp = set()\n",
    "        for x in arr:\n",
    "            tmp = {x & o for o in tmp}\n",
    "            tmp.add(x)\n",
    "            ans |= tmp\n",
    "        return min(abs(x - target) for x in ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, init, unitX, f):\n",
    "        self.unitX = unitX  # empty/fill value\n",
    "        self.f = f  # (X, X) -> X, with f(UnitX, x) = x\n",
    "        if type(init) == int:\n",
    "            self.n = 1 << (init - 1).bit_length()\n",
    "            self.X = [unitX] * (self.n * 2)\n",
    "        else:\n",
    "            self.n = 1 << (len(init) - 1).bit_length()\n",
    "            # init == X[n:len(init)]\n",
    "            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))\n",
    "            for i in range(self.n - 1, 0, -1):\n",
    "                self.X[i] = self.f(self.X[i * 2], self.X[i * 2 | 1])    # i -> (2i, 2i+1)\n",
    "  \n",
    "    def query(self, l, r):  # [l, r]\n",
    "        l += self.n\n",
    "        r += self.n\n",
    "        al = ar = self.unitX\n",
    "        while l <= r:\n",
    "            if l & 1:\n",
    "                al = self.f(al, self.X[l])\n",
    "                l += 1\n",
    "            if r & 1 == 0:\n",
    "                ar = self.f(self.X[r], ar)\n",
    "                r -= 1\n",
    "            l >>= 1\n",
    "            r >>= 1\n",
    "        return self.f(al, ar)\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        mask = (1 << 24) - 1\n",
    "        tree = SegmentTree(arr, mask, lambda x,y: x & y)\n",
    "        ans = abs(-10**9 - target)\n",
    "        def f(l, r):\n",
    "            if l < 0 or r < l:\n",
    "                return -10**9\n",
    "            return tree.query(l, r)\n",
    "        \n",
    "        for r in range(n):\n",
    "            if target - arr[r] >= ans: continue\n",
    "            if tree.query(0,r) - target >= ans: continue\n",
    "            i = bisect.bisect_left(range(r+1), target, key=lambda l: tree.query(l,r))\n",
    "            ans = min(ans, abs(f(i-1, r) - target), abs(f(i, r) - target))\n",
    "            if ans == 0: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        counter = logTrick(arr, lambda x, y: x & y)\n",
    "        return min(abs(k - target) for k in counter)\n",
    "\n",
    "\n",
    "from typing import Callable, DefaultDict, List, Optional, Tuple\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "def logTrick(\n",
    "    nums: List[int],\n",
    "    op: Callable[[int, int], int],\n",
    "    f: Optional[Callable[[List[Tuple[int, int, int]], int], None]] = None,\n",
    ") -> DefaultDict[int, int]:\n",
    "    \"\"\"\n",
    "    将 `nums` 的所有非空子数组的元素进行 `op` 操作，返回所有不同的结果和其出现次数.\n",
    "\n",
    "    Args:\n",
    "        nums: 1 <= len(nums) <= 1e5.\n",
    "        op: 与/或/gcd/lcm 中的一种操作，具有单调性.\n",
    "\n",
    "    Returns:\n",
    "        所有不同的结果和其出现次数\n",
    "    \"\"\"\n",
    "    res = defaultdict(int)\n",
    "    dp = []\n",
    "    for pos, cur in enumerate(nums):\n",
    "        for i in range(len(dp)):\n",
    "            dp[i][0] = op(dp[i][0], cur)\n",
    "        dp.append([cur, pos, pos + 1])\n",
    "\n",
    "        ptr = 0\n",
    "        for v in dp[1:]:\n",
    "            if dp[ptr][0] != v[0]:\n",
    "                ptr += 1\n",
    "                dp[ptr] = v\n",
    "            else:\n",
    "                dp[ptr][2] = v[2]\n",
    "\n",
    "        dp = dp[: ptr + 1]\n",
    "        for v in dp:\n",
    "            res[v[0]] += v[2] - v[1]\n",
    "        if f is not None:\n",
    "            f(dp, pos + 1)\n",
    "\n",
    "    return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        mx = max(arr).bit_length()\n",
    "        d = defaultdict(list)\n",
    "        for i, j in enumerate(arr):\n",
    "            for k in range(mx):\n",
    "                if (j >> k) & 1 == 0:\n",
    "                    d[k].append(i)\n",
    "        L = set(arr)\n",
    "        for i, j in enumerate(arr):\n",
    "            dd = SortedDict()\n",
    "            start = j\n",
    "            for k in range(mx):\n",
    "                if (start >> k) & 1:\n",
    "                    idx = bisect_left(d[k], i)\n",
    "                    if idx == len(d[k]):\n",
    "                        continue\n",
    "                    if d[k][idx] in dd:\n",
    "                        dd[d[k][idx]].append(k)\n",
    "                    else:\n",
    "                        dd[d[k][idx]] = [k]\n",
    "            for kk, vv in dd.items():\n",
    "                for vvv in vv:\n",
    "                    start ^= (1 << vvv)\n",
    "                L.add(start)\n",
    "        L.add(-inf)\n",
    "        L.add(inf)\n",
    "        L = sorted(L)\n",
    "        id = bisect_left(L, target)\n",
    "        return min(L[id] - target, target - L[id - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        if target in arr:return 0\n",
    "        n = len(arr)\n",
    "        F = [0] * 4 * n\n",
    "        def build(o,l,r):\n",
    "            if l == r:F[o] = arr[l];return\n",
    "            m = (l+r) >> 1\n",
    "            build(2*o,l,m)\n",
    "            build(2*o+1,m+1,r)\n",
    "            F[o] = F[2*o] & F[2*o+1]\n",
    "            return\n",
    "        build(1,0,n-1)\n",
    "        def query(o,l,r,a,b):\n",
    "            if a > b:return 10000000\n",
    "            if a <= l and r <= b:return F[o]\n",
    "            m = (l+r) >> 1;res = (1<<30)-1\n",
    "            if a <= m:\n",
    "                res &= query(2*o,l,m,a,b)\n",
    "            if b >= m+1:\n",
    "                res &= query(2*o+1,m+1,r,a,b)\n",
    "            return res\n",
    "        \n",
    "        l,r,temp,res = 0,1,arr[0],abs(arr[0]-target)\n",
    "        for i in arr:res = min(res,abs(i-target))\n",
    "        while r < n or (temp < target and l < r-1):\n",
    "            if temp == target:return 0\n",
    "            if temp < target and l < r-1:\n",
    "                l += 1\n",
    "                temp = query(1,0,n-1,l,r-1)\n",
    "            else:\n",
    "                temp &= arr[r]\n",
    "                r += 1\n",
    "            res = min(res,abs(temp - target))\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        if target in arr:return 0\n",
    "        n = len(arr)\n",
    "        F = [0] * 4 * n\n",
    "        def build(o,l,r):\n",
    "            if l == r:F[o] = arr[l];return\n",
    "            m = (l+r) >> 1\n",
    "            build(2*o,l,m)\n",
    "            build(2*o+1,m+1,r)\n",
    "            F[o] = F[2*o] & F[2*o+1]\n",
    "            return\n",
    "        build(1,0,n-1)\n",
    "        def query(o,l,r,a,b):\n",
    "            if a <= l and r <= b:return F[o]\n",
    "            m = (l+r) >> 1;res = (1<<30)-1\n",
    "            if a <= m:\n",
    "                res &= query(2*o,l,m,a,b)\n",
    "            if b >= m+1:\n",
    "                res &= query(2*o+1,m+1,r,a,b)\n",
    "            return res\n",
    "        \n",
    "        l,r,temp,res = 0,1,arr[0],abs(arr[0]-target)\n",
    "        while r < n or (r == n and (temp <= target)):\n",
    "            if temp == target:return 0\n",
    "            if temp < target:\n",
    "                if l < r:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    l += 1;r += 1\n",
    "                temp = query(1,0,n-1,l,r-1)\n",
    "            else:\n",
    "                temp &= arr[r]\n",
    "                r += 1\n",
    "            res = min(res,abs(temp - target))\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        if target in arr:return 0\n",
    "        n = len(arr)\n",
    "        F = [0] * 4 * n\n",
    "        def build(o,l,r):\n",
    "            if l == r:F[o] = arr[l];return\n",
    "            m = (l+r) >> 1\n",
    "            build(2*o,l,m)\n",
    "            build(2*o+1,m+1,r)\n",
    "            F[o] = F[2*o] & F[2*o+1]\n",
    "            return\n",
    "        build(1,0,n-1)\n",
    "        def query(o,l,r,a,b):\n",
    "            if a <= l and r <= b:return F[o]\n",
    "            m = (l+r) >> 1;res = (1<<30)-1\n",
    "            if a <= m:\n",
    "                res &= query(2*o,l,m,a,b)\n",
    "            if b >= m+1:\n",
    "                res &= query(2*o+1,m+1,r,a,b)\n",
    "            return res\n",
    "        \n",
    "        l,r,temp,res = 0,1,arr[0],abs(arr[0]-target)\n",
    "        for i in arr:res = min(res,abs(i-target))\n",
    "        while r < n or (r == n and (temp <= target)):\n",
    "            if temp == target:return 0\n",
    "            if temp < target:\n",
    "                if l < r:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    l += 1;r += 1\n",
    "                temp = query(1,0,n-1,l,r-1)\n",
    "            else:\n",
    "                temp &= arr[r]\n",
    "                r += 1\n",
    "            res = min(res,abs(temp - target))\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestToTarget(self, arr: List[int], target: int) -> int:\n",
    "        n = len(arr)\n",
    "        st = [0] * (4 * n + 1)\n",
    "        maxval = (1 << 22) - 1\n",
    "\n",
    "        def build(node = 1, left = 0, right = n - 1):\n",
    "            if left == right:\n",
    "                st[node] = arr[right]\n",
    "                return \n",
    "            mid = left + right >> 1\n",
    "            build(node * 2, left, mid)\n",
    "            build(node * 2 + 1, mid + 1, right)\n",
    "            st[node] = st[node * 2] & st[node * 2 + 1]\n",
    "\n",
    "        def query(L, R, node = 1, left = 0, right = n - 1):\n",
    "            if right < L or left > R: return maxval\n",
    "            if left >= L and right <= R: return st[node]\n",
    "            mid = left + right >> 1\n",
    "            return query(L, R, node * 2, left, mid) & query(L, R, node * 2 + 1, mid + 1, right)\n",
    "\n",
    "        build()\n",
    "        res = inf\n",
    "        left = right = 0\n",
    "        while right < n:\n",
    "            m = query(left, right)\n",
    "            if m < target:\n",
    "                left += 1\n",
    "            else:\n",
    "                right += 1\n",
    "            res = min(res,abs(m - target))\n",
    "      \n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
